#include <stdio.h>  
#include <stdlib.h>  
#include <string.h> 
#include <ctype.h> 
#include "../../../stl/include/map.h"  
#include "../../../stl/include/set.h"  
#include "../../../stl/include/vector.h"  
#ifdef _WIN32
#include <windows.h>
#endif

// 定义文法符号类型  
typedef enum { TERMINAL, NON_TERMINAL } SymbolType;  

// 文法符号结构体  
typedef struct {  
    char* name;  
    SymbolType type;  
} Symbol;  

// 产生式结构体  
typedef struct {  
    Symbol left;  // 左部非终结符  
    Vector* right;  // 右部符号串  
} Production;  

// LL(1)分析器结构体  
typedef struct {  
    Vector* productions;  
    Set* terminals;  
    Set* nonTerminals;  
    Symbol startSymbol;  
    
    // FIRST集和FOLLOW集  
    Map* firstSets;  
    Map* followSets;  
    
    // 预测分析表  
    Map* parsingTable;  
    const char *strat;
    const char *end;
} LL1Parser;  

// 符号比较函数  
int symbolCompare(const void* a, const void* b) {  
    Symbol* s1 = (Symbol*)a;  
    Symbol* s2 = (Symbol*)b;  
    if (s1->type != s2->type) return s1->type - s2->type;  
    return strcmp(s1->name, s2->name);  
}  

// 创建新符号  
Symbol* newSymbol(const char* name, SymbolType type) {  
    Symbol* sym = (Symbol*)malloc(sizeof(Symbol));  
    sym->name = strdup(name);  
    sym->type = type;  
    return sym;  
}  

// 创建新产生式  
Production* newProduction(Symbol left, Vector* right) {  
    Production* prod = (Production*)malloc(sizeof(Production));  
    prod->left = left;  
    prod->right = right;  
    return prod;  
}  

// 初始化LL(1)分析器  
LL1Parser* newLL1Parser(Symbol start,const char* start_str,const char* end_str) {  
    LL1Parser* parser = (LL1Parser*)malloc(sizeof(LL1Parser));  
    parser->productions = vector();  
    parser->terminals = set(symbolCompare);  
    parser->nonTerminals = set(symbolCompare);  
    parser->startSymbol = start;  
    parser->firstSets = map(symbolCompare);  
    parser->followSets = map(symbolCompare);  
    parser->parsingTable = map(symbolCompare);  
    parser->end=strdup(end_str);
    parser->strat=strdup(start_str);
    
    // 将开始符号加入非终结符集合  
    // parser->nonTerminals->insert(parser->nonTerminals, &start);  
    
    return parser;  
}  

// 添加产生式  
void addProduction(LL1Parser* parser, Production* prod) {  
    parser->productions->push_back(parser->productions, prod);  
    
    // 将左部非终结符加入集合  
    parser->nonTerminals->insert(parser->nonTerminals, &prod->left);  

    // 将右部符号加入终结符集合（如果是终结符）  
    for (size_t i = 0; i < prod->right->size(prod->right); i++) {  
        Symbol* sym = (Symbol*)prod->right->get(prod->right, i);  
        if (sym->type == TERMINAL) {  
            parser->terminals->insert(parser->terminals, sym);  
        }  
    }  
}  

// 计算符号串的FIRST集  
Set* computeFirstOfSequence(LL1Parser* parser, Vector* seq) {  
    Set* result = set(symbolCompare);  
    int canHaveEpsilon = 1;  
    
    for (size_t i = 0; i < seq->size(seq); i++) {  
        Symbol* sym = (Symbol*)seq->get(seq, i);  
        Set* first = (Set*)parser->firstSets->get(parser->firstSets, sym);  
        
        // 遍历FIRST(sym)中的每个符号  
        Array* firstArray = first->data(first);  
        for (size_t j = 0; j < firstArray->size; j++) {  
            Symbol* s = (Symbol*)firstArray->key[j];  
            if (strcmp(s->name, "ε") != 0) {  
                result->insert(result, s);  
            }  
        }  
        
        // 检查当前符号是否能推导出ε  
        Symbol epsilonSym = {"ε", TERMINAL};  
        if (!first->contains(first, &epsilonSym)) {  
            canHaveEpsilon = 0;  
            break;  
        }  
    }  
    
    if (canHaveEpsilon) {  
        Symbol* epsilon = newSymbol("ε", TERMINAL);  
        result->insert(result, epsilon);  
        // free(epsilon);  
    }  
    
    return result;  
}  

// 计算FIRST集  
void computeFirstSets(LL1Parser* parser) { 
    // 初始化终结符的FIRST集  
    Array* termArray = parser->terminals->data(parser->terminals);  
    for (size_t i = 0; i < termArray->size; i++) {  
        Symbol* t = (Symbol*)termArray->key[i];  
        Set* first = set(symbolCompare);  
        first->insert(first, t);  
        parser->firstSets->put(parser->firstSets, t, first);  
    }  
    
    // 初始化非终结符的FIRST集  
    Array* nonTermArray = parser->nonTerminals->data(parser->nonTerminals);  
    for (size_t i = 0; i < nonTermArray->size; i++) {  
        Symbol* nt = (Symbol*)nonTermArray->key[i];  
        parser->firstSets->put(parser->firstSets, nt, set(symbolCompare));  
    }  
    
    int changed = 1;  
    while (changed) {  
        changed = 0;  
        
        for (size_t i = 0; i < parser->productions->size(parser->productions); i++) {  
            Production* prod = (Production*)parser->productions->get(parser->productions, i);  
            Symbol left = prod->left;  
            Set* firstLeft = (Set*)parser->firstSets->get(parser->firstSets, &left);  
            
            size_t oldSize = firstLeft->size;  
            Set* firstAlpha = computeFirstOfSequence(parser, prod->right);  
            Array* firstAlphaArray = firstAlpha->data(firstAlpha);  
            
            // 将FIRST(α)中的符号加入FIRST(left)  
            for (size_t j = 0; j < firstAlphaArray->size; j++) {  
                Symbol* s = (Symbol*)firstAlphaArray->key[j];  
                
                firstLeft->insert(firstLeft, s);  
            }  
            
            if (firstLeft->size > oldSize) {  
                changed = 1;  
            }  
        }  
    }  
}  

// 计算FOLLOW集  
void computeFollowSets(LL1Parser* parser) {  
    // 初始化FOLLOW集  
    Array* nonTermArray = parser->nonTerminals->data(parser->nonTerminals);  
    for (size_t i = 0; i < nonTermArray->size; i++) {  
        Symbol* nt = nonTermArray->key[i];  
        parser->followSets->put(parser->followSets, nt, set(symbolCompare));  
    }  
    
    // 将$加入开始符号的FOLLOW集  
    Symbol *dollar =malloc(sizeof(Symbol));
    *dollar = (Symbol) {strdup(parser->end), TERMINAL};
    Set* followStart = (Set*)parser->followSets->get(parser->followSets, &parser->startSymbol);  
    followStart->insert(followStart, dollar);  
    
    int changed = 1;  
    while (changed) {  
        changed = 0;  
        
        for (size_t i = 0; i < parser->productions->size(parser->productions); i++) {  
            Production* prod = (Production*)parser->productions->get(parser->productions, i);  
            Symbol left = prod->left;  
            Set* followLeft = (Set*)parser->followSets->get(parser->followSets, &left);  
            
            for (size_t j = 0; j < prod->right->size(prod->right); j++) {  
                Symbol* B = (Symbol*)prod->right->get(prod->right, j);  
                if (B->type == NON_TERMINAL) {  
                    Set* followB = (Set*)parser->followSets->get(parser->followSets, B);  
                    size_t oldSize = followB->size;  
                    
                    // 计算FIRST(β)，其中β是B后面的符号串  
                    Vector* beta = vector();  
                    for (size_t k = j + 1; k < prod->right->size(prod->right); k++) {  
                        prod->right->push_back(beta, prod->right->get(prod->right, k));  
                    }  
                    
                    Set* firstBeta = computeFirstOfSequence(parser, beta);  
                    Array* firstBetaArray = firstBeta->data(firstBeta);  
                    
                    // 将FIRST(β)的非ε元素加入FOLLOW(B)  
                    for (size_t k = 0; k < firstBetaArray->size; k++) {  
                        Symbol* s = (Symbol*)firstBetaArray->key[k];  
                        if (strcmp(s->name, "ε") != 0) {  
                            
                            followB->insert(followB, s);  
                        }  
                    }  
                    
                    // 如果FIRST(β)包含ε，或者β为空，将FOLLOW(A)加入FOLLOW(B)  
                    Symbol epsilon = {"ε", TERMINAL};  
                    if (firstBeta->contains(firstBeta, &epsilon) || beta->size(beta) == 0) {  
                        for (size_t k = 0; k < followLeft->data(followLeft)->size; k++) {  
                            Symbol* s = (Symbol*)followLeft->data(followLeft)->key[k];  
                            
                            followB->insert(followB, s);  
                        }  
                    }  
                    
                    if (followB->size > oldSize) {  
                        changed = 1;  
                    }  
                }  
            }  
        }  
    }  
}  

// 构建预测分析表
void buildParsingTable(LL1Parser* parser) {  
    // 获取非终结符集合  
    Array* nonTermArray = parser->nonTerminals->data(parser->nonTerminals);  
    // 遍历所有非终结符  
    for (size_t i = 0; i < nonTermArray->size; i++) {  
        Symbol* nt = (Symbol*)nonTermArray->key[i];  
        // 为每个非终结符创建内层Map  
        Map* innerMap = map(symbolCompare);  
        
        // 获取终结符集合  
        Array* termArray = parser->terminals->data(parser->terminals);  
        // printf("%d\n",termArray->size);
        // 遍历所有终结符  
        for (size_t j = 0; j < termArray->size; j++) {  
            Symbol* t = (Symbol*)termArray->key[j];  
            // 初始化表项为NULL  
            // printf("%s,%s\n", nt->name, t->name);  
            innerMap->put(innerMap, t, NULL);  
        }  
        
        // 添加$终结符  
        Symbol *dollar =malloc(sizeof(Symbol));
        *dollar = (Symbol) {strdup(parser->end), TERMINAL};
        innerMap->put(innerMap, dollar, NULL);  
        
        // 将内层Map添加到外层Map  
        parser->parsingTable->put(parser->parsingTable, nt, innerMap);  
    }  
    
    // 填充预测分析表  
    for (size_t i = 0; i < parser->productions->size(parser->productions); i++) {  
        Production* prod = (Production*)parser->productions->get(parser->productions, i);  
        Vector* right = prod->right;  
        
        Set* firstAlpha = computeFirstOfSequence(parser, right);  
        Array* firstAlphaArray = firstAlpha->data(firstAlpha);  
        
        // 对于FIRST(α)中的每个终结符a，将A→α加入M[A,a]  
        for (size_t j = 0; j < firstAlphaArray->size; j++) {  
            Symbol* a = (Symbol*)firstAlphaArray->key[j];  
            if (strcmp(a->name, "ε") != 0) {  
                Map* row = (Map*)parser->parsingTable->get(parser->parsingTable, &prod->left);  
                if (row->get(row, a) != NULL) { 
                    fprintf(stderr, "冲突: 文法不是LL(1)的\n");  
                    return;  
                }  
                row->put(row, a, prod);  
            }  
        }  
        
        // 如果ε在FIRST(α)中，对于FOLLOW(A)中的每个终结符b(包括$)，将A→α加入M[A,b]  
        Symbol epsilon = {"ε", TERMINAL};  
        if (firstAlpha->contains(firstAlpha, &epsilon)) {  
            Set* followA = (Set*)parser->followSets->get(parser->followSets, &prod->left);  
            Array* followArray = followA->data(followA);  
            
            for (size_t j = 0; j < followArray->size; j++) {  
                Symbol* b = (Symbol*)followArray->key[j];  
                Map* row = (Map*)parser->parsingTable->get(parser->parsingTable, &prod->left);  
                
                if (row->get(row, b) != NULL) {  
                    fprintf(stderr, "冲突: 文法不是LL(1)的\n");  
                    return;  
                }  
                row->put(row, b, prod);  


            }  
        }   
    }  
}  

// 打印FIRST集  
void printFirstSets(LL1Parser* parser) { 
    printf("文法分析结果:\n");  
    fflush(stdout);
    printf("FIRST集:\n");  
    fflush(stdout);
    Array* nonTermArray = parser->nonTerminals->data(parser->nonTerminals);  
    
    for (size_t i = 0; i < nonTermArray->size; i++) {  
        Symbol* nt = (Symbol*)nonTermArray->key[i];  
        Set* first = (Set*)parser->firstSets->get(parser->firstSets, nt);  
        Array* firstArray = first->data(first);  
        
        printf("FIRST(%s) = { ", nt->name);  
        for (size_t j = 0; j < firstArray->size; j++) {  
            Symbol* s = (Symbol*)firstArray->key[j];  
            printf("%s ", s->name);  
        }  
        printf("}\n");  
        fflush(stdout);
    }  
}  

// 打印FOLLOW集  
void printFollowSets(LL1Parser* parser) {  
    printf("FOLLOW集:\n");  
    fflush(stdout);
    Array* nonTermArray = parser->nonTerminals->data(parser->nonTerminals);  
    
    for (size_t i = 0; i < nonTermArray->size; i++) {  
        Symbol* nt = (Symbol*)nonTermArray->key[i];  
        Set* follow = (Set*)parser->followSets->get(parser->followSets, nt);  
        Array* followArray = follow->data(follow);  
        printf("FOLLOW(%s) = { ", nt->name);  
        for (size_t j = 0; j < followArray->size; j++) { 
            Symbol* s = malloc(sizeof(Symbol));
            s=(Symbol*)followArray->key[j];  
            printf("%s ", s->name);  
        }  
        printf("}\n"); 
        fflush(stdout); 
    }  
}  

// 打印产生式  
void printProduction(const Production* prod) {  
    char buffer[256] = {0};  
    char* ptr = buffer;  
    
    // 构建产生式字符串  
    ptr += snprintf(ptr, sizeof(buffer), "%s->", prod->left.name);  
    for (size_t i = 0; i < prod->right->size(prod->right); i++) {  
        Symbol* sym = (Symbol*)prod->right->get(prod->right, i);  
        ptr += snprintf(ptr, sizeof(buffer) - (ptr - buffer), "%s", sym->name);  
    }  
    
    // 统一格式输出  
    printf("%-15s", buffer);
    fflush(stdout);  
}  

// 打印预测分析表
void printParsingTable(LL1Parser* parser) {  
    printf("\n预测分析表:\n");  
    fflush(stdout);
    // 获取所有终结符（包括$）  
    Set* allTerms = set(symbolCompare);  
    Array* termArray = parser->terminals->data(parser->terminals);  
    for (size_t i = 0; i < termArray->size; i++) {  
        allTerms->insert(allTerms, termArray->key[i]);  
    }  
    Symbol dollar = {strdup(parser->end), TERMINAL};  
    allTerms->insert(allTerms, &dollar);  
    
    // 打印表头  
    printf("非终结符\\终结符\n\t");  
    fflush(stdout);
    Array* terms = allTerms->data(allTerms);  
    for (size_t i = 0; i < terms->size; i++) {  
        Symbol* t = (Symbol*)terms->key[i];  
        printf("%-15s", t->name);  
    }  
    printf("\n");  
    fflush(stdout);
    // 打印表内容  
    Array* nonTerms = parser->nonTerminals->data(parser->nonTerminals);  
    for (size_t i = 0; i < nonTerms->size; i++) {  
        Symbol* nt = (Symbol*)nonTerms->key[i];  
        printf("%s\t", nt->name);  
        
        Map* row = (Map*)parser->parsingTable->get(parser->parsingTable, nt);  
        for (size_t j = 0; j < terms->size; j++) {  
            Symbol* t = (Symbol*)terms->key[j];  
            Production* prod = (Production*)row->get(row, t);  
            
            if (prod != NULL) {  
                printProduction(prod); 
            }else{
                printf("%-15s","null");
            }
            fflush(stdout);
        }  
        printf("\n"); 
        fflush(stdout); 
    }  

}  

// 释放LL1Parser资源  
void freeLL1Parser(LL1Parser* parser) {  
    // 释放产生式  
    for (size_t i = 0; i < parser->productions->size(parser->productions); i++) {  
        Production* prod = (Production*)parser->productions->get(parser->productions, i);  
        prod->right->clear(prod->right);  
        free(prod->right);  
        free(prod);  
    }  
    parser->productions->clear(parser->productions);  
    free(parser->productions);  
    
    // 释放集合  
    parser->terminals->clear(parser->terminals);  
    free(parser->terminals);  
    parser->nonTerminals->clear(parser->nonTerminals);  
    free(parser->nonTerminals);  
    
    // 释放FIRST和FOLLOW集  
    Array* firstKeys = parser->firstSets->data(parser->firstSets);  
    for (size_t i = 0; i < firstKeys->size; i++) {  
        Symbol* key = (Symbol*)firstKeys->key[i];  
        Set* s = (Set*)parser->firstSets->get(parser->firstSets, key);  
        s->clear(s);  
        free(s);  
    }  
    parser->firstSets->clear(parser->firstSets);  
    free(parser->firstSets);  
    
    Array* followKeys = parser->followSets->data(parser->followSets);  
    for (size_t i = 0; i < followKeys->size; i++) {  
        Symbol* key = (Symbol*)followKeys->key[i];  
        Set* s = (Set*)parser->followSets->get(parser->followSets, key);  
        s->clear(s);  
        free(s);  
    }  
    parser->followSets->clear(parser->followSets);  
    free(parser->followSets);  
    
    // 释放预测分析表  
    Array* tableKeys = parser->parsingTable->data(parser->parsingTable);  
    for (size_t i = 0; i < tableKeys->size; i++) {  
        Symbol* key = (Symbol*)tableKeys->key[i];  
        Map* row = (Map*)parser->parsingTable->get(parser->parsingTable, key);  
        row->clear(row);  
        free(row);  
    }  
    parser->parsingTable->clear(parser->parsingTable);  
    free(parser->parsingTable);  
    
    free(parser);  
}  


// 去除字符串两端的空白字符和换行符
void trim(char *str) {
    if (str == NULL) return;

    // 去除前导空白字符
    char *start = str;
    while (isspace((unsigned char)*start)) {
        start++;
    }

    // 去除尾部空白字符
    char *end = str + strlen(str) - 1;
    while (end >= start && isspace((unsigned char)*end)) {
        end--;
    }
    *(end + 1) = '\0'; // 设置新结尾

    // 将去除前导空格后的内容移动到字符串开头
    if (start != str) {
        memmove(str, start, end - start + 1);
        str[end - start + 1] = '\0';
    }
}

// 获取规则文件并解析
LL1Parser* readGrammarFromFile(const char* filename) {
    FILE* file = fopen(filename, "r");
    if (!file) {
        perror("Error opening file");
        return NULL;
    }

    char line[256];
    Map* symbolMap = map((int (*)(const void*, const void*))strcmp);
    char* token = strtok(line, " \t\n");

    // 读取终结符（第一行）
    fgets(line, sizeof(line), file);
    trim(line);
    const char*end=strdup(line);
    // printf("%s\n",end);

    // 读取起始符号（第二行）
    fgets(line, sizeof(line), file);
    trim(line);
    const char*start=strdup(line);
    // printf("%s\n",start);

    // 跳过第三行（待解析语句）
    fgets(line, sizeof(line), file);

    // 读取终止符（第四行），确保包含ε
    fgets(line, sizeof(line), file);
    trim(line);
    // printf("%s\n",line);
    token = strtok(line, " \t\n");
    while (token) {
        Symbol* sym = malloc(sizeof(Symbol));
        *sym=(Symbol){strdup(token), TERMINAL};
        symbolMap->put(symbolMap, strdup(token), sym);
        token = strtok(NULL, " \t\n");
    }

    // 确保ε存在
    // if (!symbolMap->get(symbolMap, "ε")) {
    //     Symbol* epsilon = newSymbol("ε", TERMINAL);
    //     symbolMap->put(symbolMap, "ε", epsilon);
    // }

    // 读取非终结符（第五行）
    fgets(line, sizeof(line), file);
    trim(line);
    // printf("%s\n",line);
    token = strtok(line, " \t\n");
    while (token) {
        Symbol* sym = malloc(sizeof(Symbol));
        *sym=(Symbol){strdup(token), NON_TERMINAL};
        symbolMap->put(symbolMap, strdup(token), sym);
        token = strtok(NULL, " \t\n");
    }
    Symbol* startSym = malloc(sizeof(Symbol));
    *startSym=(Symbol){strdup(start),NON_TERMINAL};
    // 创建分析器
    LL1Parser* parser = newLL1Parser(*startSym,start,end);

    // 填充符号集合
    Array* symbols = symbolMap->data(symbolMap);
    for (size_t i = 0; i < symbols->size; i++) {
        const char* name = (const char*)symbols->key[i];
        Symbol* sym = (Symbol*)symbolMap->get(symbolMap, strdup(name));
        if (sym->type == TERMINAL) {
            parser->terminals->insert(parser->terminals, sym);
        } else {
            parser->nonTerminals->insert(parser->nonTerminals, sym);
        }
    }

    // 读取产生式规则
    while (fgets(line, sizeof(line), file)) {
        trim(line);
        // 解析产生式格式：A → α | β | ...
        char* arrow = strstr(line, "→");
        if (!arrow) arrow = strstr(line, "->");
        if (!arrow) continue;

        *arrow = '\0';
        char* lhs = strtok(line, " \t\n");
        char* rhses = arrow + (arrow[1] == '>' ? 2 : strlen("→"));

        // 处理每个候选项
        char* prod = strtok(rhses, "|");
        while (prod) {
            char *new_prod=strdup(prod);
            Vector* right = vector();
            char *save_inner;
            char *sym = strtok_r(new_prod, " \t\n", &save_inner);
            while (sym) {
                Symbol* s = symbolMap->get(symbolMap, sym);
                // printf("%s\n",s->name);
                if (!s) {
                    s=malloc(sizeof(Symbol));
                    *s=(Symbol){sym, isupper(sym[0]) ? NON_TERMINAL : TERMINAL};
                    symbolMap->put(symbolMap, strdup(sym), s);
                }
                right->push_back(right, s);
                sym = strtok_r(NULL, " \t\n", &save_inner);
            }
            Symbol* leftSym = symbolMap->get(symbolMap, lhs);
            addProduction(parser, newProduction(*leftSym, right));
            prod = strtok(NULL, "|");
        }
        // printf("\n");
    }

    fclose(file);
    return parser;
}


int main(int argc, char *argv[]) {  
    #ifdef _WIN32
    SetConsoleOutputCP(CP_UTF8);  // Windows设置控制台为UTF-8
    #endif
    // 检查参数数量
    if (argc < 2) {
        printf("用法: %s <输入参数>",argv[0]);
        return 1;
    }

    // 安全获取参数
    const char* input = argv[1];
    LL1Parser* parser=readGrammarFromFile(input);
     
    // 计算FIRST集和FOLLOW集  
    computeFirstSets(parser);  //ok
    computeFollowSets(parser);  //ok

    // 构建预测分析表  
    buildParsingTable(parser); 
    // 打印结果  
    printFirstSets(parser);  
    printFollowSets(parser);  
    printParsingTable(parser);  
    
    // 释放资源  
    freeLL1Parser(parser);  
    
    return 0;  
}  